package main

import (
	"fmt"
)

//无法理解 希尔排序， 排着 。最后数据乱了 .而后在进行的排序，数据很不稳定
// 数据不能稳定， 大在后，小在前
func ShellSortStep(arr []int, start int, gap int) {
	length := len(arr)                           //数组长度
	for i := start + gap; i < length; i += gap { //插入排序的变种
		backup := arr[i] //备份插入的数据
		j := i - gap     //上一个位置循环找到位置插入
		for j >= 0 && backup < arr[j] {
			arr[j+gap] = arr[j] //从前往后移动
			j -= gap
		}
		arr[j+gap] = backup //插入

	}
	fmt.Println("")

	fmt.Println(arr)
}

func ShellSort(arr []int) []int {
	length := len(arr) //数组长度
	if length <= 1 {
		return arr //一个元素的数组，直接返回
	} else {
		gap := length / 2
		for gap > 0 {
			for i := 0; i < gap; i++ { //处理每个元素的步长
				ShellSortStep(arr, i, gap)
			}
			//gap-- //gap--
			gap /= 2
		}

	}

	return arr
}

func main() {
	// arr := []int{3, 59, 4, 2, 9}

	arr := []int{3, 59, 18, 4, 28, 2, 9, 6, 78, 13, 16, 22}

	ShellSortStep(arr, 0, 1) // 直接调用最后一步

	//ShellSort(arr)

	fmt.Println("")

	fmt.Println(ShellSort(arr))

}
